1717D - Madoka and The Corruption Scheme - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define B break
#define C continue
#define mid ((l+r)/2)
#define left (2*idx)
#define right (2*idx+1)

using namespace std;

const ll Mod=1e9+7 , N = 500500 , inf=1e18;
ll n , m , k , q , x , y , z , a[N], fact[N], inv[N] , ans=0 , sum=0 , mn=inf , mx=0 ;

ll poww(ll a,ll b,ll Mod){
    ll res=1;if(b<0)b=(b%(Mod-1)+Mod-1)%(Mod-1);
    for(;b;b>>=1,a=1ll*a*a%Mod)
        if(b&1)res=1ll*res*a%Mod;
    return res;
}

ll Cnk(ll n,ll k){
    if(k>n)return 0;
    return (((fact[n]*inv[k])%Mod) * inv[n-k])%Mod;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fact[0]=1;
    for(ll i=1 ; i<N ; i++)     fact[i] = (fact[i-1]*i)%Mod;

    inv[N-1] = poww(fact[N-1],-1,Mod);
    for(ll i=N-2 ; i>=0 ; i--)  inv[i] = (inv[i+1]*(i+1))%Mod;

    int t=1;
    //cin >> t ;
    while(t--){
        bool ok=1;
        cin >> n >> k ;
        ans=0;
        for(int i=0 ; i<=k && i<=n ; i++){
            ans += Cnk(n,i);
            ans %= Mod;
        }
        cout << ans << endl;
    }
    return 0;
}